package leetcode.d_1_99;

import java.util.Arrays;

// https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
// 在排序数组中找到第一个和最后一个出现的位置
public class P34 {
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int first = search(nums, target, true);
            int last = search(nums, target, false) - 1;
            if (first <= last && nums[first] == target && nums[last] == target) {
                return new int[]{first, last};
            }
            return new int[]{-1, -1};
        }

        public int search(int[] nums, int target, boolean isLower) {
            int left = 0;
            int right = nums.length - 1;
            int res = nums.length;
            while(left <= right) {
                int mid = left + (right-left) / 2;
                if (nums[mid] >= target && isLower || (nums[mid]>target)) {
                    res = mid;
                    right = mid - 1;

                }else {
                    left = mid + 1;
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        P34.Solution solution = new P34().new Solution();
        System.out.println(Arrays.toString(solution.searchRange(new int[]{5,7,7,8,8,10}, 8))); // [3, 4]
    }
}
